package com.lry.basic.algorithm.tree;


import java.util.LinkedList;
import java.util.Stack;

public class BiTree1<T> {

    public Node<T> buildTreeByPreAndInOrder(T[]preOrder,T[]inOrder){
        if(null==preOrder||preOrder.length==0||
           null==inOrder||inOrder.length==0||
            inOrder.length!=preOrder.length){
            return null;
        }
        return coreBuildTreeByPreAndInOrder(preOrder,0,preOrder.length-1,
                                            inOrder,0,inOrder.length-1);
    }

    /**
     *
     * @param preOrder 前序序列
     * @param preStart 前序开始节点
     * @param preEnd 前序最后节点
     * @param inOrder 中序序列
     * @param inStart 中序开始节点
     * @param inEnd 中序最后节点
     * @return
     *
     * 1,2,4,3,5前
     * 4,2,1,3,5中
     */

    private Node<T> coreBuildTreeByPreAndInOrder(T[] preOrder, int preStart, int preEnd, T[] inOrder, int inStart, int inEnd) {
        Node root = new Node(preOrder[preStart]);
        //叶子节点直接返回
        if(preStart==preEnd&&inStart==inEnd){
            return root;
        }

        //找到根节点在中序序列的下标
        int rootIndex = 0;
        for(;rootIndex<=inEnd;++rootIndex){
            if(preOrder[preStart]==inOrder[rootIndex]){
                break;
            }
        }
        //左子树长度
        int leftLen = rootIndex - inStart;
        //右子树长度
        int rightLen = inEnd - rootIndex;

        if(leftLen>0){
            root.left = coreBuildTreeByPreAndInOrder(preOrder,preStart+1,preStart+leftLen,
                                                     inOrder,inStart,rootIndex-1);
        }
        if(rightLen>0){
            root.right = coreBuildTreeByPreAndInOrder(preOrder,preStart+leftLen+1,preEnd,
                                                      inOrder,rootIndex+1,inEnd);
        }
        return root;
    }

    public void preOrder(Node root){
        if(root!=null){
            System.out.print(root.data+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    public void inOrder(Node root){
        if(root!=null){
            preOrder(root.left);
            System.out.print(root.data+" ");
            preOrder(root.right);
        }
    }
    public void postOrder(Node root){
        if(root!=null){
            preOrder(root.left);
            preOrder(root.right);
            System.out.print(root.data+" ");
        }
    }

    public void preOrderV2(Node root){
        if(null==root)
            return;
        LinkedList<Node> stack = new LinkedList<Node>();
        while(root!=null||!stack.isEmpty()){
            while(root!=null){
                System.out.print(root.data+" ");
                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                root = stack.pop();
                root = root.right;
            }
        }
    }

    public int high(Node root){
        if(null==root)
            return 0;
        return Math.max(high(root.left),high(root.right))+1;
    }

    public int balance(Node root){
        if(root==null)
            return 0;
        return Math.abs(high(root.left)-high(root.right));
    }

    public boolean isBalance(Node root){
        if(null==root)
            return true;
        LinkedList<Node> stack = new LinkedList<Node>();
        while(root!=null||!stack.isEmpty()){
            while(root!=null){
                if(balance(root)>1){
                    return false;
                }
                stack.push(root);
                root = root.left;
            }
            if(!stack.isEmpty()){
                root = stack.pop();
                root = root.right;
            }
        }
        return true;
    }


    public boolean isBalanced(Node root) {
        return help(root) != -1;
    }

    int help(Node root){
        if (root == null) return 0;
        int left = help(root.left);
        if (left == -1) return -1;
        int right = help(root.right);
        if (right == -1) return -1;
        if (Math.abs(left - right) > 1) return -1;
        return Math.max(left, right)+1;
    }

    public static void main(String[] args) {
        BiTree1<Integer> tree = new BiTree1();
        Node root = tree.buildTreeByPreAndInOrder(new Integer[]{1,2,4,3,5},new Integer[]{4,2,1,3,5});
        tree.preOrder(root);
        System.out.println();
        tree.inOrder(root);
        System.out.println();
        tree.postOrder(root);
        System.out.println();
        tree.preOrderV2(root);
        System.out.println();
        System.out.println(tree.high(root));
        System.out.println(tree.isBalance(root));
        System.out.println(tree.isBalanced(root));
    }
    static class Node<T>{
        Node left;
        Node right;
        T data;
        public Node(T data){
            this.data = data;
        }
    }
}
